// 有一个只含有 'Q', 'W', 'E', 'R' 四种字符，且长度为 n 的字符串。
//
// 假如在该字符串中，这四个字符都恰好出现 n/4 次，那么它就是一个「平衡字符串」。 
//
// 
//
// 给你一个这样的字符串 s，请通过「替换一个子串」的方式，使原字符串 s 变成一个「平衡字符串」。 
//
// 你可以用和「待替换子串」长度相同的 任何 其他字符串来完成替换。 
//
// 请返回待替换子串的最小可能长度。 
//
// 如果原字符串自身就是一个平衡字符串，则返回 0。 
//
// 
//
// 示例 1： 
//
// 输入：s = "QWER"
//输出：0
//解释：s 已经是平衡的了。 
//
// 示例 2： 
//
// 输入：s = "QQWE"
//输出：1
//解释：我们需要把一个 'Q' 替换成 'R'，这样得到的 "RQWE" (或 "QRWE") 是平衡的。
// 
//
// 示例 3： 
//
// 输入：s = "QQQW"
//输出：2
//解释：我们可以把前面的 "QQ" 替换成 "ER"。 
// 
//
// 示例 4： 
//
// 输入：s = "QQQQ"
//输出：3
//解释：我们可以替换后 3 个 'Q'，使 s = "QWER"。
// 
//
// 
//
// 提示： 
//
// 
// 1 <= s.length <= 10^5 
// s.length 是 4 的倍数 
// s 中只含有 'Q', 'W', 'E', 'R' 四种字符 
// 
// Related Topics 双指针 字符串 
// 👍 61 👎 0


package cn.db117.leetcode.solution12;

/**
 * 1234.替换子串得到平衡字符串.replace-the-substring-for-balanced-string
 *
 * @author db117
 * @since 2021-06-21 15:35:44
 **/

public class Solution_1234 {
    public static void main(String[] args) {
        Solution solution = new Solution_1234().new Solution();
        System.out.println(solution.balancedString("QWER"));
        System.out.println(solution.balancedString("QQWE"));
        System.out.println(solution.balancedString("QQQW"));
        System.out.println(solution.balancedString("QQQQ"));
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int balancedString(String s) {
            char[] chars = s.toCharArray();
            int len = chars.length;
            int ave = len / 4;

            // 统计每一个字符的数量
            //4 16 17 22
            int[] count = new int[26];

            for (char c : chars) {
                count[c - 'A']++;
            }
            // 本来就是
            if (count[4] == ave && count[16] == ave && count[17] == ave && count[22] == ave) {
                return 0;
            }

            // 滑动窗口,计算窗口外面的字符数量小于平均值
            // 如果外面的字符数量小于平均值,则只需替换窗口里面的字符

            int left = 0, min = Integer.MAX_VALUE;

            for (int right = 0; right < len; right++) {
                char c = chars[right];

                // 外面的字符数量减一
                count[c - 'A']--;

                while (left <= right && count[4] <= ave && count[16] <= ave && count[17] <= ave && count[22] <= ave) {
                    // 当前区间大小
                    min = Math.min(min, right - left + 1);
                    // 区间外的字符数量增加
                    count[chars[left] - 'A']++;
                    left++;
                }


            }

            return min;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}